package com.sheng.leetcode.year2023.month01.day30;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/01/30
 * <p>
 * 1669. 合并两个链表<p>
 * <p>
 * 给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。<p>
 * 请你将 list1 中下标从 a 到 b 的全部节点都删除，并将list2 接在被删除节点的位置。<p>
 * 下图中蓝色边和节点展示了操作后的结果：<p>
 * 请你返回结果链表的头指针。<p>
 * <p>
 * 示例 1：<p>
 * 输入：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]<p>
 * 输出：[0,1,2,1000000,1000001,1000002,5]<p>
 * 解释：我们删除 list1 中下标为 3 和 4 的两个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。<p>
 * <p>
 * 示例 2：<p>
 * 输入：list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]<p>
 * 输出：[0,1,1000000,1000001,1000002,1000003,1000004,6]<p>
 * 解释：上图中蓝色的边和节点为答案链表。<p>
 * <p>
 * 提示：<p>
 * 3 <= list1.length <= 10^4<p>
 * 1 <= a <= b < list1.length - 1<p>
 * 1 <= list2.length <= 10^4<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/merge-in-between-linked-lists">1669. 合并两个链表</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1669 {

    @Test
    public void test01() {
//        ListNode list1 = new ListNode(0, new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5))))));
//        ListNode list2 = new ListNode(1000000, new ListNode(1000001, new ListNode(1000002)));
//        int a = 3, b = 4;

        ListNode list1 = new ListNode(0, new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6)))))));
        ListNode list2 = new ListNode(1000000, new ListNode(1000001, new ListNode(1000002, new ListNode(1000003, new ListNode(1000004)))));
        int a = 2, b = 5;

        ListNode listNode = new Solution().mergeInBetween(list1, a, b, list2);
        System.out.println(listNode.toString());
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        // list1 链表去掉 a , b 之后的左部分
        ListNode left = list1;
        // list1 链表去掉 a , b 之后的右部分
        ListNode right = list1;
        for (int i = 0; i < a - 1; i++) {
            left = left.next;
        }
        // 获取左部分之后在左部分后面拼接上 list2
        left.next = list2;
        for (int i = 0; i < b + 1; i++) {
            right = right.next;
        }
        // 寻找 list2 的最后一个结点，拼接上右部分
        while (list2.next != null) {
            list2 = list2.next;
        }
        list2.next = right;
        return list1;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
